1. Field of the Invention
The present invention relates to imaging technology. More specifically, the present invention relates to the method of halftoning a color image.
2. Related Art
Error diffusion is a high quality method for halftoning an image. Halftoning is the process where a grayscale image is converted to a binary image for the purpose of rendering on a binary device such as a printer. It is assumed that 255 represents a printer dot and 0 represents no printer dot. Error diffusion halftoning diffuses the quantization error at a given image pixel to future unprocessed image pixels. A naive extension of grayscale error diffusion to color is to process the cyan (C), magenta (M), yellow (Y) and black (K) planes independently using a grayscale error diffusion halftoning algorithm. However, such an approach ignores the correlation among the color planes and produces undesirable color halftone noise due to the unintended overlapping of color dots from the different planes. For example a light gray tone of 10% C, 10% M and 10% Y will result in identical dot placement and thus produce composite black dots (C=M=Y=255) on a light background, resulting in an undesirable high contrast pattern. A more pleasing pattern of dots is to print 10% C, 10% M and 10% Y dots without any overlap, so that the color variation is minimized while still reproducing the graytone. The present invention produces smooth color patterns with minimized color fluctuation. The colors allowed at a particular color tone are determined by the luminance level of the tone. The rendered color is chosen as the color in the set of colors allowed that minimizes the perceived color difference using a weighted CIELab error metric. The quantization errors are diffused in the colorant space although quantization is performed in CIELab. The invention may be regarded as an extension (in spirit) of the invention described in J. Allebach and Q. Lin, “Joint design of color dither matrices for a set of colorants”, patent application, HP PDNO 10951098-1,1997 (which designed dither matrices to minimize color fluctuation) to error diffusion. Due to the properties of error diffusion the invention typically produces higher quality sharper results than algorithms based on dither matrices.
One of the common ways of halftoning a color image is to compare the image with a dither matrix, and either print a dot or not print a dot depending on the outcome of the comparison. Previously, a method of designing a set of color dither matrices jointly was described. The dither matrices were designed to minimize colorimetric perceptual color fluctuation in CIELab color space. A tone ramp of uniform gray tones exclusively along the black-white tone axis was used to jointly generate C, M and Y dither matrices. When applied to an image it is still possible for the algorithm to produce undesirable color fluctuation since:                1. An image does not have only uniform regions, and may have rapidly changing colors and edge gradients.        2. Colors occur which do not lie on the black-white axis.        
Case 1 for example, causes a loss in spatial resolution along edges in the image and causes the image sharpness to be compromised. Case 2 indicates that undesirable color fluctuations could occur when the dither matrices are applied in regions where the colors deviate appreciably from the black-white axis. These drawbacks of using dither matrices in general. Since the dither matrices are pre-designed they have low complexity and are easy to implement. However pre-designed dither matrices are not able to adapt to the color tones as they occur in an image. This motivates the use of error diffusion. The present invention retains (conceptually) the general properties of the jointly designed dither matrices (a.k.a. color smooth dither) in error diffusion, such as perceptual color fluctuation minimization in CIELab space and control of the colors permitted at a given gray tone. The invention described accomplishes these objectives by performing quantization in a CIELab space and defining the colors allowed not only along the black-white axis but for arbitrary color tones.
Previous color error diffusion algorithms such as R. Klassen and K. Bharat, “Vector error diffusion in a distorted color space,” and C. Y. Kim, I. Kweon and Y. S. Seo, “Color and printer models for color halftoning,” perform quantization and diffusion of quantization errors in either the device independent nonlinear CIELab space, or the linear device independent XYZ space. In each case the nearest color dot to the current modified input pixel (current pixel under consideration modified by adding a filtered version of past quantization errors) is determined in the CIELab or the XYZ space and the error is then diffused using the same space. Error diffusion filtering assumes color coordinates that are linearly related linearly to luminance. This excludes the CIELab space for diffusing quantization errors. The linear XYZ space is suitable for diffusion of the quantization errors but does not account for the nonlinear nature of the human visual system. The present invention performs quantization in device independent CIELab color space but diffuses the quantization error in the device dependent CMYK color space. The device CMYK printer space (after appropriate color matching) has an approximately linear relationship between color coordinates and luminance. While the diffusion could theoretically also be done in the device independent XYZ space, the distorted gamut of the color dots in XYZ space results in significant gamut mismatch errors producing color shifts in the output halftone. The device CMYK space has a robust cubical gamut. Diffusion in CMYK also gives us the key advantage of being able to produce color smooth clustered dot halftones for robust printing on laser printers and printers with high dot gain characteristics via a simple modification of the invention. Such an approach is not known in either the CIELab or XYZ color space diffusion systems. Recently, Lau et al “Digital color halftoning with generalized error diffusion and multi-channel green-noise masks” extended Levin's work (“Output dependent feedback in error diffusion halftoning”) on producing error diffused halftones with clustered dots, to color images. The invention described here extends to color clustered dot halftoning by incorporating output dependent feedback into the color smooth error diffusion framework. Thus the present invention controls the color reproduction, color smoothness and the overlap of arbitrary secondary and tertiary colors. Thus in a given color tone the present invention could allow C, M, Y, R, G apart from white and not allow any other colors. Such flexibility is not possible with the method of Lau. Lau's algorithm does not consider calorimetric color reproduction at all. The present invention uses a weighted CIELab decision space instead of the usual CIELab space. The present invention gives luminance errors a greater weight but still considers the chrominance contribution to the color fluctuation. Finally, the present invention controls the colors allowed in the halftone depending on the input color tone. Thus a tone of 10% C, 20% M and 30% C will be halftoned exclusively with C, M and Y dots only without overlap. Thus the quantization is done under the constraint that the output dot be restricted one out of a set of allowed colors. This set may vary depending on the color pixel being halftoned. Such an approach while retaining colorimetric color reproduction capability also produces smooth color patterns with minimized perceptual fluctuation without compromising image sharpness. It is to be noted that the present invention works with an arbitrary number of device dependent process colors which may or may not include the often used CMYK color space which we use here as an example of a device dependent color space.
The complexity of implementing the invention may be reduced by observing that the unintended overlap or clumping of C and M dots producing blue (B) is the most undesirable. Thus a reasonable approach is to halftone the C and M planes in a plane dependent manner and halftone the Y and K planes independently. Here the assumption is that the colors red (R) and green (G) produced due to the overlap of M and Y and C and Y respectively are produce less visible color variation in comparison with blue and composite black dots. Since on most inkjets the K dots could be designed to be sparse by appropriate color separation, the K plane is also processed independently. Typically several comparisons and/or computations are performed to determine if a C dot, an M dot or a B dot should be placed at a given location. The present invention folds these computations/comparisons into a few lookup tables (LUTs). In the present invention, based on the current tone a LUT is selected from a bank of LUTs and the output dot is directly determined by using the C and M modified input values to lookup the appropriate color dot to be placed. Thus the computational effort involved goes into designing the LUTs and may be performed offline. Thus the present invention provides significant speedup over conventional implementations, especially when implemented in software.